/*
 * @Author: 缄默
 * @Date: 2021-11-11 19:44:36
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 21:24:18
 */


//在二叉树中找到两个节点的最近公共祖先
//简单查询 未进行优化

#include "../../DataStructure/tree.hpp"


using namespace std;

TreeNode* lowestAncestor(TreeNode* head, int o1, int o2);

int main() {
    vector<int> preOrder({4, 2, 1, 0, 3, 6, 5, 7});
    vector<int> inOrder({0, 1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    cout << lowestAncestor(head, 1, 3)->val << endl;
    return 0;
}

TreeNode* lowestAncestor(TreeNode* head, int o1, int o2) {
    if (head == nullptr || head->val == o1 || head->val == o2) return head;
    TreeNode* left = lowestAncestor(head->left, o1, o2);
    TreeNode* right = lowestAncestor(head->right, o1, o2);
    if (left != nullptr && right != nullptr) {
        return head;
    }
    return left == nullptr ? right : left;
}
